package algorithm.swordoff;

import java.util.Arrays;

/**
 * n个骰子的点数
 * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
 * 感觉又是一个回溯题,组合
 */

public class SQ60 {
    public double[] dicesProbability2(int n) {
        double[] ans = new double[6 * n + 1];
        backTrack(ans, 1.0, 0, 0, n);
        return Arrays.copyOfRange(ans, n , 6 * n + 1);

    }

    public double[] dicesProbability(int n) {
        double[] ans = new double[6];
        Arrays.fill(ans, 1.0/6);
        // 迭代每个骰子
        for (int i = 2; i <= n; i++) {
            double[] temp = new double[5*i+1];

            // 遍历上一轮的dp数组
            for (int j = 0; j < ans.length ; j++) {

                // 遍历骰子可能的所有点数,注意K为什么不是从1到7,因为这几个dp数组的索引需要看成左端对齐
                for (int k = 0; k < 6; k++) {
                    // 上一个dp数组的某个位置即ans[j]对下一个dp数组的6个位置有贡献
                    temp[j+k] += ans[j]/6.0;
                }
            }
            ans = temp;

        }
        return ans;

    }

    /**
     * 相当于暴力法,太慢
     * @param ans 全局解,变量
     * @param probability 掷出当前点数序列的概率(序列由于不需要遂不保存),变量
     * @param diceSum 当前点数序列之和,变量
     * @param hasRolled 已经掷了几个骰子,变量
     * @param diceNum 总共的骰子数量,常量
     */
    private void backTrack(double[] ans,
                           double probability,
                           int diceSum,
                           int hasRolled,
                           int diceNum) {

        if (hasRolled == diceNum) {
            ans[diceSum] += probability;
            return;
        }

        for (int i = 1; i < 7; i++) backTrack(ans,probability/6.0, diceSum+i, hasRolled+1, diceNum);
    }

    public static void main(String[] args) {
        SQ60 sq60 = new SQ60();
        System.out.println(Arrays.toString(sq60.dicesProbability2(2)));
        System.out.println(Arrays.toString(sq60.dicesProbability(2)));
    }
}

// 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]


